package com.c2b.algorithm.leetcode.base;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href="https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/">从前序与中序遍历序列构造二叉树(Construct Binary Tree from Preorder and Inorder Traversal)</a>
 * <p>给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1:
 *      输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
 *      输出: [3,9,20,null,null,15,7]
 *
 * 示例 2:
 *      输入: preorder = [-1], inorder = [-1]
 *      输出: [-1]
 *     </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>1 <= preorder.length <= 3000</li>
 *         <li>inorder.length == preorder.length</li>
 *         <li>-3000 <= preorder[i], inorder[i] <= 3000</li>
 *         <li>preorder 和 inorder 均 无重复 元素</li>
 *         <li>inorder 均出现在 preorder</li>
 *         <li>preorder 保证 为二叉树的前序遍历序列</li>
 *         <li>inorder 保证 为二叉树的中序遍历序列</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @see LC0105ConstructBinaryTreeFromPreorderAndInorderTraversal_M
 * @see LC0106ConstructBinaryTreeFromInorderAndPostorderTraversal_M
 * @see LC0889ConstructBinaryTreeFromPreorderAndPostorderTraversal_M
 * @since 2023/11/3 9:50
 */
public class LC0105ConstructBinaryTreeFromPreorderAndInorderTraversal_M {

    static class Solution {
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < inorder.length; i++) {
                map.put(inorder[i], i);
            }
            return doBuildTree(0, inorder.length - 1, 0, preorder, map);
        }

        /**
         * 构建二叉树。
         * <p>前序遍历：根->左->右</p>
         * <p>中序遍历：左->根->右</p>
         * <p>由前序遍历可以确定根节点的值，并根据根节点的值在中序遍历中找到对应位置；将中序遍历结果分为左根右三部分。
         * 根节点的值用来构建根节点，左用来构建左子树，右用来构建右子树</p>
         *
         * @param inorderLeftBorder     构建当前树时中序遍历左边界
         * @param inorderRightBorder    构建当前树时中序遍历右边界
         * @param rootIndexInPreorder   前序遍历根节点所在的索引位置
         * @param preorder              前序遍历集
         * @param inorderValue2IndexMap 中序遍历值与下标的映射关系
         * @return 构建后的二叉树
         */
        private TreeNode doBuildTree(int inorderLeftBorder, int inorderRightBorder, int rootIndexInPreorder, int[] preorder, Map<Integer, Integer> inorderValue2IndexMap) {
            // 结束条件
            if (inorderLeftBorder > inorderRightBorder) {
                return null;
            }
            // 前序遍历的最左位置的元素即为根节点的值
            TreeNode root = new TreeNode(preorder[rootIndexInPreorder]);
            // 在中序遍历中，找到根节点的位置。以该节点位置为界，分别构建左右子树
            int index = inorderValue2IndexMap.get(root.val);
            // 构建左子树。左子树的根节点为前序遍历中，根节点的下一个节点
            root.left = doBuildTree(inorderLeftBorder, index - 1, rootIndexInPreorder + 1, preorder, inorderValue2IndexMap);
            // 构建右子树。右子树的根节点为：在前序遍历中，根节点所在位置 + 左子树节点的个数(中序遍历根节点所在位置-左边界) + 1(下一个位置)
            root.right = doBuildTree(index + 1, inorderRightBorder, rootIndexInPreorder + (index - inorderLeftBorder) + 1, preorder, inorderValue2IndexMap);
            // 回溯返回根节点
            return root;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        TreeNode.printTree(solution.buildTree(new int[]{3, 9, 20, 15, 7}, new int[]{9, 3, 15, 20, 7}));
    }
}
